package linkedlist.other;

import linkedlist.Node;
import linkedlist.iterator.LoopIterator;

/**
 * @Author wangtengyu
 * @Create 2018-09-05-15:42
 * <p>
 * <p>
 * 常规来说，删除一个链表中的指定节点，得到该节点的上一个节点，进行指向，该操作需要顺序查找，时间复杂度为o（n） 现在要求时间复杂度为o（1）的情况下进行删除
 * 获得待删除节点的下一个节点，然后把该节点的数据和指向复制到当前待删除节点 特殊情况：1.待删除节点是尾节点 时间复杂度还需要o（n） 2.链表只有一个节点
 */
public class DeleteNode {


  public void deleteNode(Node head, Node deleteNode) {
    if (head == null || deleteNode == null) {
      return;
    }

    if (head == deleteNode) {
      head = null;
    }

    //复制下一个节点
    if (deleteNode.getNext() != null) {
      Node next = deleteNode.getNext();
      deleteNode.setData(next.getData());
      deleteNode.setNext(next.getNext());
    } else if (deleteNode.getNext() == null) {
      Node prev = head;
      while (prev.getNext() != deleteNode) {
        prev = prev.getNext();
      }
      prev.setNext(null);
    }
  }


  public static void main(String[] args) {
    LoopIterator iterator = new LoopIterator();
    DeleteNode deleter = new DeleteNode();

    Node a = new Node(1, null);
    Node b = new Node(2, a);
    Node c = new Node(3, b);
    Node d = new Node(4, c);

    iterator.iterator(d);
    deleter.deleteNode(d, b);
    System.out.println();
    iterator.iterator(d);


  }

}
